/**
 * @author VernHe
 * @date 2021年08月27日 11:16
 */

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution_0437 {
    public int pathSum(TreeNode root, int targetSum) {
        return pathSum(root, targetSum, new int[1000], 0);
    }

    /**
     * 统计路径和等于sargetSum的个数
     *
     * @param node      当前正遍历到的节点
     * @param targetSum 目标值
     * @param path      路径
     * @param level     当前层数（也是路径的下标）
     * @return 符合要求的路径个数
     */
    private int pathSum(TreeNode node, int targetSum, int[] path, int level) {
        // 递归基
        if (node == null) {
            return 0;
        }
        // 初始化符合要求的路径个数。
        // 特殊情况：当前节点刚好等于targetSum
        int count = node.val == targetSum ? 1 : 0;
        // 用于累加的临时变量
        int temp = node.val;
        // 以当前节点为根节点开始沿着路径path往前一个个去找是否有符合要求的路径
        for (int i = level - 1; i >= 0; i--) {
            temp += path[i];
            if (temp == targetSum) {
                // 找到符合要求的路径了
                count++;
            }
        }
        // 在继续往下递归之前，要记录当前节点的值
        path[level] = node.val;
        // 继续递归，分别以当前节点的左右节点为根节点往前查找
        int leftCount = pathSum(node.left, targetSum, path, level + 1);
        int rightCount = pathSum(node.right, targetSum, path, level + 1);

        return count + leftCount + rightCount;
    }
}
